package cn.dlc.com.graph;

import cn.dlc.com.queue.Queue;
import lombok.Data;

/**
 * @author 邓立川
 * @date 2021/3/29 21:35
 * @desc 深度优先搜索
 */
@Data
public class DepthFirstSearch {

    // 索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    // 记录有多少个顶点与s顶点相通
    private int count ;

    // 找到G图中s顶点相通的顶点
    public DepthFirstSearch(Graph G, int s){
        // 初始化marked，有多少个顶点，就有多少个值
        this.marked = new boolean[G.getV()];
        //
        this.count = 0;
        // 直接调用方法，获取相通的点
        dfs(G, s);
    }

    // 深度优先遍历
    private void dfs(Graph G,int s){

        // 首先将当前节点标记为已经检测
        marked[s] = true;

        //拿到当前节点的邻接链表
        Queue<Integer> queue = G.adj(s);

        for (Integer w : queue) {
            // 拿到顶点
            if(!this.marked(w)) {
                // 没有检测过,继续标记
                dfs(G, w);
            }
        }
        // 数量增加
        count++;
    }

    // 是否与s相连通。
    public boolean marked(int v) {
        return marked[v];
    }

    // 连接点的个数
    public int count(){
        return count;
    }
}
